# ---
# title: 926. Flip String to Monotone Increasing
# id: problem926
# author: Tian Jun
# date: 2020-10-31
# difficulty: Medium
# categories: Array
# link: <https://leetcode.com/problems/flip-string-to-monotone-increasing/description/>
# hidden: true
# ---
# 
# A string of `'0'`s and `'1'`s is _monotone increasing_ if it consists of some
# number of `'0'`s (possibly 0), followed by some number of `'1'`s (also
# possibly 0.)
# 
# We are given a string `S` of `'0'`s and `'1'`s, and we may flip any `'0'` to a
# `'1'` or a `'1'` to a `'0'`.
# 
# Return the minimum number of flips to make `S` monotone increasing.
# 
# 
# 
# **Example 1:**
# 
#     
#     
#     Input: "00110"
#     Output: 1
#     Explanation: We flip the last digit to get 00111.
#     
# 
# **Example 2:**
# 
#     
#     
#     Input: "010110"
#     Output: 2
#     Explanation: We flip to get 011111, or alternatively 000111.
#     
# 
# **Example 3:**
# 
#     
#     
#     Input: "00011000"
#     Output: 2
#     Explanation: We flip to get 00000000.
#     
# 
# 
# 
# **Note:**
# 
#   1. `1 <= S.length <= 20000`
#   2. `S` only consists of `'0'` and `'1'` characters.
# 
# 
## @lc code=start
using LeetCode

## add your code here:
## @lc code=end
